package main

import (
	"fmt"
	"math/rand"
	"time"
)

const (
	n = 10000
)

func bubbleSort(data []int, length int) {
	if length < 2 || len(data) <= 1 {
		return
	}
	for i := 0; i < length-1; i++ {
		for j := 0; j < length-i-1; j++ {
			if data[j] > data[j+1] {
				data[j], data[j+1] = data[j+1], data[j]
			}
		}
	}
}
func insertSort(data []int, length int) {
	if length < 2 || len(data) <= 1 {
		return
	}
	var i int
	var j int
	for i = 1; i < length; i++ {
		temp := data[i]
		for j = i - 1; j >= 0 && data[j] > temp; j-- {

			data[j+1] = data[j]

		}
		data[j+1] = temp
	}
}
func partition(data []int, left int, right int, length int) (result int) {
	if left < 0 || right >= length || length <= 1 || len(data) <= 1 {
		return
	}
	index := left + rand.Intn(right-left+1)
	privit := data[index]
	data[index], data[right] = data[right], data[index]
	i := left - 1
	//j := right
	for k := left; k < right; k++ {
		if data[k] < privit {
			i = i + 1
			if i != k {
				data[i], data[k] = data[k], data[i]
			}
		}
	}
	i = i + 1
	data[i], data[right] = data[right], data[i]
	return i

}
func quickSort(data []int, left int, right int, length int) {
	if left == right {
		return
	}
	if right-left == 1 {
		if data[left] > data[right] {
			data[left], data[right] = data[right], data[left]
		}
		return
	}
	index := partition(data, left, right, length)
	if index > left {
		quickSort(data, left, index-1, length)
	}
	if right > index {
		quickSort(data, index+1, right, length)
	}
}
func testBubbleSort() {
	var data [n]int
	for i := 0; i < n; i++ {
		data[i] = rand.Intn(10000) + 1

	}
	t1 := time.Now().UnixNano()
	bubbleSort(data[:n], n)
	t2 := time.Now().UnixNano()
	fmt.Println(t2 - t1)
}
func testInsertSort() {
	var data [n]int
	for i := 0; i < n; i++ {
		data[i] = rand.Intn(10000) + 1

	}
	t1 := time.Now().UnixNano()
	insertSort(data[:n], n)
	t2 := time.Now().UnixNano()
	fmt.Println(t2 - t1)
	//fmt.Println(data)
}
func testQuickSort() {
	var data [n]int
	for i := 0; i < n; i++ {
		data[i] = rand.Intn(10000) + 1

	}
	t1 := time.Now().UnixNano()
	quickSort(data[:n], 0, n-1, n)
	t2 := time.Now().UnixNano()
	fmt.Println(t2 - t1)
	//fmt.Println(data)
}
func main() {
	testBubbleSort()
	testInsertSort()
	testQuickSort()

}
